The present invention relates generally to data processing systems and methods, and more particularly to a method for online presorting and reduction of data to be processed.
Data processing systems typically receive information that is subsequently processed. For example, receiver systems often receive pulse data from a broad range of frequencies received in different directions.
As described in xe2x80x9cPulse Radarxe2x80x9d by Marvin L. Belcher and Josh T. Nessmith (CRC Press LLC, 1997), which is hereby incorporated by reference herein, the digital processing in a radar system often includes signal processing and data processing. Signal data received by an antenna is sent in digital form to a signal processor, where the signal data can be filtered using a fast Fourier transform (FFT) to reduce computational requirements. The output of the signal processor can be characterized in terms of range gates and Doppler filters corresponding to the range and Doppler resolution, respectively. The output data is then sent to a radar data processor, typically a general purpose computer with a realtime operating system. These data processors can range from microcomputers to mainframes, depending upon the requirements of the radar system.
The radar data filtering using the fast Fourier transform however is applied in the same way to a stream of input data, which is not presorted or prefiltered.
Other data processing systems reduce or compress data using compression schemes. Input audio and video signals can be converted to digital signals which then are compressed, for example, using a coding scheme based on, for example, special waveforms or Fourier transforms. These coding or compression schemes thus reduce the amount of digital data corresponding to the audio and video signals, so that the data can be transmitted more quickly over a certain bandwidth and adequately reproduced at an output.
These coding systems as well are applied in the same way to a stream input data and do not intelligently presort the data or reduce redundant data.
It is advantageous to presort data an to reduce redundant data so that subsequent computational requirements can be reduced. This presorting and reduction is especially advantageous when operating in a high dense signal environment.
The present invention provides a method of sorting and reducing data in which a so-called cell control block array is created so as to form a histogram. The histogram thus has a plurality of cell control blocks, each of which corresponds to a corresponding cell classifiable as core or non-core and used or unused. Each of the plurality of cell control blocks has a cell counter, with the cell counter being incremented if the corresponding cell is identified by an input event. Each of the plurality of cell control blocks also has a first link word for pointing to a start of a data output chain if the corresponding cell is used and core, and each of the plurality of cell control blocks has a second link word for pointing to a related core cell if the corresponding cell is used and non-core. The histogram is a function of at least one parameter including a first parameter and has a first lower limit and a first upper limit for the first parameter. The input data is received as a function of the at least one parameter so as to form a plurality of event descriptor blocks, with the at least one parameter including the first parameter. The method then determines whether each of the plurality of event descriptor blocks corresponds to one of the plurality of cell control blocks within the histogram, and, if so, determines whether the corresponding cell of the one cell control block is used or unused. If the corresponding cell is unused, a classification of the corresponding cell in the cell control block is changed from unused to used. The input data of the plurality of event descriptor blocks is then output to an output data array as a function of the first and second link words.
Thus, the input data is sorted into data output chains formed around core cells. This sorting can be especially advantageous in reducing the computational requirements for detection systems such as radar warning equipment, electronic measurement equipment and electronic intelligence equipment, as events with similar parameter values can be grouped.
The method may provide that at least one parameter further includes a second parameter. The desired parameters advantageously can be selected during an initialization period.
The method may also provide that the outputting of the input data occurs after a certain time period, a so-called dwell period. This time period can be predefined, and can range from milliseconds to hours or days, depending on the application. For example, if the method of the present invention is used in a detection system, presorting of data related to detection of astronomical events advantageously may have very long dwell periods, while some radar applications advantageously may have very short dwell periods.
During an initialization period before the dwell period, the plurality of cell control blocks advantageously are classified as unused.
During the dwell period, an event may occur which corresponds to a first cell control block of the cell control blocks. This first cell control block is surrounded in the histogram by surrounding cell control blocks of the plurality of cell control blocks. The method of the present invention then may include that if the first control block cell is determined as unused, it is further determined if at least one of the surrounding cell control blocks is used. If all of the surrounding cell control blocks are unused, the first cell control block designates its corresponding cell as core. However, if one or more of the surrounding cell control blocks is used, the first cell control block is linked to the core cell of the first used surrounding cell.
If the first cell control block identified by an event is determined as used, it is further determined whether the first cell control block corresponds to a core cell or a non-core cell. If the first cell control block is a core cell and a data limit set by the method of the present invention is exceeded, then the event is counted; no further action is taken and the next input data are read. If the first cell control block correspond to a non-core cell, a link is obtained for the first cell control block to indicate the related core cell.
In this way, the events are sorted so that core and related cells are grouped so they can be output as data chains with similar parameter characteristics. Data reduction is performed through the limits.
The histogram may be n-dimensional and with n being one or more. Preferably, the histogram has at least two dimensions, as at least two parameters are desirable for most applications in sorting and grouping the data.
The histogram thus may be divided between the first lower limit and the first upper limit into 2k columns, k being a number of bits of the first parameter used in the determining whether each of the plurality of event descriptor blocks corresponds to one of the plurality of control block cells.
The method of the present invention advantageously can be used in a detection system, such as a system using radar warning equipment, electronic support measurement equipment, or electronic intelligence equipment. The parameters of the method can thus include a propagated frequency of signals or waves measured by the detection system and a measured direction of arrival of the signals or waves.
The present invention thus provides for reduction of redundant or unnecessary data in high signal density environments of detection systems. In electromagnetic environments in which signal density may exceed several million events per second, this reduction in required processing needs can eliminate or reduce overloads in subsequent data processing equipment. This is especially so if the equipment is covering a broad instantaneous RF and angle range, and even more so if high powered RF emitters are being used.
The input data in the form of event descriptor blocks of the present invention may be received from a parameter or signal measurement facility, such as a pulse extractor. The event descriptor block is a vector containing at least one parameter. In a preferred embodiment, the event descriptor block is a vector containing at least two parameters, such as for example the frequency of the signal received and the angle or measured direction of the signal received. Other parameters which could be included in the event descriptor block include amplitude of the signal, the time of arrival, and the width of the pulse in which the signal is received.
The event descriptor blocks may be stored before sorting in a FIFO memory which operates as a buffer.
The method of the present invention can reside in a storage medium such as a memory as a set of instructions capable of being executed by a processor.